package leetcode.D400.T347;

import java.util.*;

class Solution {
    /* 桶排序解法
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        int maxSize = 0;
        for(int i=0; i<nums.length; ++i) {
           map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
           maxSize = Math.max(maxSize, map.get(nums[i]));
        }
        List<Integer>[] buckets = new List[maxSize];
        Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()) {
            Map.Entry<Integer, Integer> item = iterator.next();
            int count = item.getValue(), num = item.getKey();
            if(buckets[count-1] == null) {
                buckets[count-1] = new LinkedList<>();
            }
            buckets[count-1].add(num);
        }
        for(int i=buckets.length-1; i>=0; --i) {
            if(buckets[i] == null) {
                continue;
            }
            for (Integer num : buckets[i]) {
                result[--k] = num;
            }
            if(k <= 0) {
                break;
            }
        }
        return result;
    }*/
    // 优先队列解法（堆）
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[k];
        for (int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });
        for(Integer key: map.keySet()) {
            if(pq.size() < k) {
                pq.add(key);
            } else if(map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        while(!pq.isEmpty()) {
            result[--k] = pq.remove();
        }
        return result;
    }
}